//
//  ProblemOffer47.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/25.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 47. 礼物的最大价值
 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

 示例 1:
 输入:
 [
   [1,3,1],
   [1,5,1],
   [4,2,1]
 ]
 输出: 12
 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
 */
@objcMembers class ProblemOffer47: NSObject {
    func solution() {
        print(maxValue([[1,3,1]]))
        print(maxValue([[1,3,1],[1,5,1]]))
        print(maxValue([[1,3,1],[1,5,1],[4,2,1]]))
    }
    
    /*
     动态规划
     1: 创建一个二位数组 dp[m][n]
     2: dp[i][j] 从[0][0]到达[i][j]位置右下角最大的礼物价值
     3: dp[i][j] = grid[i][j] + max(dp[i][j-1], dp[i-1][j])
     */
    func maxValue(_ grid: [[Int]]) -> Int {
        if grid.count == 0 {
            return 0
        } else if grid.count == 1 {
            return grid[0].reduce(0) { (first, second) -> Int in
                return first + second
            }
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: grid[0].count), count: grid.count)
        dp[0][0] = grid[0][0]
        
        return getMaxValue(grid, &dp, grid.count-1, grid[0].count-1)
    }
    func getMaxValue(_ grid: [[Int]], _ dp: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i == 0, j == 0 {
            return dp[0][0]
        } else if i < 0 || j < 0 {
            return Int.min
        }
        
        if dp[i][j] > 0 {
            return dp[i][j]
        }
        
        dp[i][j] = grid[i][j] + max(getMaxValue(grid, &dp, i, j-1), getMaxValue(grid, &dp, i-1, j))
        return dp[i][j]
    }
}
